﻿#include <iostream>

using namespace std;

void printfArray(int *array, int length) {
    for (int i = 0; i < length; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void mergerArray(int *array, int left, int right) {
    int temp[right - left + 1];
    int middle = (left + right) / 2;

    int i = left;
    int j = middle + 1;
    int count = 0;
    while (i <= middle && j <= right) {
        if (array[i] <= array[j]) {
            temp[count++] = array[i++];
        } else {
            temp[count++] = array[j++];
        }
    }
    while (i <= middle) temp[count++] = array[i++];
    while (j <= right) temp[count++] = array[j++];

    for (i = left; i <= right; ++i) {
        array[i] = temp[i - left];
    }
}

void mergerSort(int *array, int left, int right) {
    if (right <= left) {
        return;
    }

    int middle = (left + right) / 2;
    mergerSort(array, left, middle);
    mergerSort(array, middle + 1, right);

    mergerArray(array, left, right);
}

int main() {
    int array[] = {2, 4, 6, 7, 3, 2, 5, 6, 7, 2, 2, 4, 2, 1, 4, 1, 6, 7, 9, 0, 8};
    int length = (sizeof(array) / sizeof(int));
    cout << "length = " << length << endl;

    cout << "排序前: ";
    printfArray(array, length);

    mergerSort(array, 0, length - 1);

    cout << "排序后: ";
    printfArray(array, length);

    return 0;
}